package com.hy.dp.bagProblem.multipleBag;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MultipleBag {

    /**
     * 多重背包
     * 对于多重背包，我在力扣上还没发现对应的题目，所以这里就做一下简单介绍，大家大概了解一下。
     *
     * 有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
     *
     * 多重背包和01背包是非常像的， 为什么和01背包像呢？
     *
     * 每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。
     *
     *  例如：
     * 背包最大重量为10。
     *
     * 物品为：
     *
     * 重量	   价值	数量
     * 物品0	1	15	2
     * 物品1	3	20	3
     * 物品2	4	30	2
     * 问背包能背的物品最大价值是多少？
     *
     * 和如下情况有区别么？
     *
     * 重量	   价值	数量
     * 物品0	1	15	1
     * 物品0	2	20	1
     * 物品1	3	30	1
     *
     * 毫无区别，这就转成了一个01背包问题了，且每个物品只用一次。
     *
     * 方法一： 改变物品数量为01背包格式
     * 方法二： 就是把每种商品遍历的个数放在 01背包(物品不重复) 里面在遍历一遍。
     *
     * 从代码里可以看出是01背包里面在加一个for循环遍历一个每种商品的数量。 和01背包还是如出一辙的。
     *
     * 当然还有那种二进制优化的方法，其实就是把每种物品的数量，打包成一个个独立的包。
     *
     * @return
     */
    // 版本一：改变物品数量为01背包格式
    public static int multipleBag01(){
        List<Integer> weight = new ArrayList<>(Arrays.asList(1, 3, 4));
        List<Integer> value = new ArrayList<>(Arrays.asList(15, 20, 30));
        List<Integer> nums = new ArrayList<>(Arrays.asList(2, 3, 2));
        int bagWeight = 10;

        int [] dp = new int[bagWeight + 1];
        // 把物品展开为i
        for (int i = 0; i < nums.size(); i++) {
            if (nums.get(i) > 1){
                weight.add(weight.get(i));
                value.add(value.get(i));
                nums.set(i,nums.get(i) - 1);
            }
        }

        //循环遍历 转换成  01背包
        for (int i = 0; i < weight.size(); i++) {
            for (int j = bagWeight; j >= weight.get(i); j--) {
                dp[j] = Math.max(dp[j],dp[j - weight.get(i)] + value.get(i));
            }
        }
        return dp[bagWeight];
    }

    //版本二：就是把每种商品遍历的个数放在 01背包(物品不重复) 里面在遍历一遍。
    public static int multipleBag02(int [] weight,int [] value,int [] nums,int bagSize){
        // 1. 定义dp数组
        int [] dp = new int[bagSize + 1];
        // 2. 推导 递推式
        //dp[j] = Math.max(dp[j],dp[j - k * weight[i]] + k * value[i]);
        // 3.初始化
        // 4.循环遍历  先遍历物品   再遍历背包  (01背包)
        for (int i = 0; i < weight.length; i++) {
            for (int j = bagSize; j >= weight[i]; j--) {
                // 以上为01背包，然后加一个遍历个数
                for (int k = 1; k <= nums[i] && j >= k * weight[i]; k++) {
                    dp[j] = Math.max(dp[j],dp[j - k * weight[i]] + k * value[i]);
                }
            }
        }
        // 5.结果推导
        return dp[bagSize];
    }

    public static void main(String[] args) {
        // 物品
        int [] weight = {1, 3, 4};
        // 价值
        int [] value = {15, 20, 30};
        // 数量
        int [] nums = {2, 3, 2};
        // 背包 容量
        int bagSize = 10;
        System.out.println("res 将多重背包转换成01背包："+multipleBag01());
        System.out.println("res 把每种商品遍历的个数放在 01背包(物品不重复) 里面在遍历一遍 "+multipleBag02(weight,value,nums,bagSize));
    }
}
